home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / a_utils / flex / amiga / flex.lha / Flex.src.lha / tblcmp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-13  |  24.7 KB  |  931 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. #ifndef lint
  30. static char rcsid[] =
  31.     "@(#) $Header: /usr/fsys/odin/a/vern/flex/RCS/tblcmp.c,v 2.5 90/06/27 23:48:38 vern Exp $ (LBL)";
  32. #endif
  33.  
  34. #include "flexdef.h"
  35.  
  36. #ifdef AMIGA
  37. #include "tblcmp.i" /* Include the prototypes */
  38. #include "misc.i"
  39. #include "dfa.i"
  40. #endif
  41.  
  42. /* declarations for functions that have forward references */
  43.  
  44. void mkentry PROTO((register int*, int, int, int, int));
  45. void mkprot PROTO((int[], int, int));
  46. void mktemplate PROTO((int[], int, int));
  47. void mv2front PROTO((int));
  48. int tbldiff PROTO((int[], int, int[]));
  49.  
  50.  
  51. /* bldtbl - build table entries for dfa state
  52.  *
  53.  * synopsis
  54.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  55.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  56.  *
  57.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  58.  * gives the number of the state to enter for a given equivalence class.
  59.  * totaltrans is the total number of transitions out of the state.  Comstate
  60.  * is that state which is the destination of the most transitions out of State.
  61.  * Comfreq is how many transitions there are out of State to Comstate.
  62.  *
  63.  * A note on terminology:
  64.  *    "protos" are transition tables which have a high probability of
  65.  * either being redundant (a state processed later will have an identical
  66.  * transition table) or nearly redundant (a state processed later will have
  67.  * many of the same out-transitions).  A "most recently used" queue of
  68.  * protos is kept around with the hope that most states will find a proto
  69.  * which is similar enough to be usable, and therefore compacting the
  70.  * output tables.
  71.  *    "templates" are a special type of proto.  If a transition table is
  72.  * homogeneous or nearly homogeneous (all transitions go to the same
  73.  * destination) then the odds are good that future states will also go
  74.  * to the same destination state on basically the same character set.
  75.  * These homogeneous states are so common when dealing with large rule
  76.  * sets that they merit special attention.  If the transition table were
  77.  * simply made into a proto, then (typically) each subsequent, similar
  78.  * state will differ from the proto for two out-transitions.  One of these
  79.  * out-transitions will be that character on which the proto does not go
  80.  * to the common destination, and one will be that character on which the
  81.  * state does not go to the common destination.  Templates, on the other
  82.  * hand, go to the common state on EVERY transition character, and therefore
  83.  * cost only one difference.
  84.  */
  85.  
  86. void bldtbl( state, statenum, totaltrans, comstate, comfreq )
  87. int state[], statenum, totaltrans, comstate, comfreq;
  88.  
  89.     {
  90.     int extptr, extrct[2][CSIZE + 1];
  91.     int mindiff, minprot, i, d;
  92.     int checkcom;
  93.  
  94.     /* If extptr is 0 then the first array of extrct holds the result of the
  95.      * "best difference" to date, which is those transitions which occur in
  96.      * "state" but not in the proto which, to date, has the fewest differences
  97.      * between itself and "state".  If extptr is 1 then the second array of
  98.      * extrct hold the best difference.  The two arrays are toggled
  99.      * between so that the best difference to date can be kept around and
  100.      * also a difference just created by checking against a candidate "best"
  101.      * proto.
  102.      */
  103.  
  104.     extptr = 0;
  105.  
  106.     /* if the state has too few out-transitions, don't bother trying to
  107.      * compact its tables
  108.      */
  109.  
  110.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  111.     mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  112.  
  113.     else
  114.     {
  115.     /* checkcom is true if we should only check "state" against
  116.      * protos which have the same "comstate" value
  117.      */
  118.  
  119.     checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  120.  
  121.     minprot = firstprot;
  122.     mindiff = totaltrans;
  123.  
  124.     if ( checkcom )
  125.         {
  126.         /* find first proto which has the same "comstate" */
  127.         for ( i = firstprot; i != NIL; i = protnext[i] )
  128.         if ( protcomst[i] == comstate )
  129.             {
  130.             minprot = i;
  131.             mindiff = tbldiff( state, minprot, extrct[extptr] );
  132.             break;
  133.             }
  134.         }
  135.  
  136.     else
  137.         {
  138.         /* since we've decided that the most common destination out
  139.          * of "state" does not occur with a high enough frequency,
  140.          * we set the "comstate" to zero, assuring that if this state
  141.          * is entered into the proto list, it will not be considered
  142.          * a template.
  143.          */
  144.         comstate = 0;
  145.  
  146.         if ( firstprot != NIL )
  147.         {
  148.         minprot = firstprot;
  149.         mindiff = tbldiff( state, minprot, extrct[extptr] );
  150.         }
  151.         }
  152.  
  153.     /* we now have the first interesting proto in "minprot".  If
  154.      * it matches within the tolerances set for the first proto,
  155.      * we don't want to bother scanning the rest of the proto list
  156.      * to see if we have any other reasonable matches.
  157.      */
  158.  
  159.     if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  160.         { /* not a good enough match.  Scan the rest of the protos */
  161.         for ( i = minprot; i != NIL; i = protnext[i] )
  162.         {
  163.         d = tbldiff( state, i, extrct[1 - extptr] );
  164.         if ( d < mindiff )
  165.             {
  166.             extptr = 1 - extptr;
  167.             mindiff = d;
  168.             minprot = i;
  169.             }
  170.         }
  171.         }
  172.  
  173.     /* check if the proto we've decided on as our best bet is close
  174.      * enough to the state we want to match to be usable
  175.      */
  176.  
  177.     if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  178.         {
  179.         /* no good.  If the state is homogeneous enough, we make a
  180.          * template out of it.  Otherwise, we make a proto.
  181.          */
  182.  
  183.         if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  184.         mktemplate( state, statenum, comstate );
  185.  
  186.         else
  187.         {
  188.         mkprot( state, statenum, comstate );
  189.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  190.         }
  191.         }
  192.  
  193.     else
  194.         { /* use the proto */
  195.         mkentry( extrct[extptr], numecs, statenum,
  196.              prottbl[minprot], mindiff );
  197.  
  198.         /* if this state was sufficiently different from the proto
  199.          * we built it from, make it, too, a proto
  200.          */
  201.  
  202.         if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  203.         mkprot( state, statenum, comstate );
  204.  
  205.         /* since mkprot added a new proto to the proto queue, it's possible
  206.          * that "minprot" is no longer on the proto queue (if it happened
  207.          * to have been the last entry, it would have been bumped off).
  208.          * If it's not there, then the new proto took its physical place
  209.          * (though logically the new proto is at the beginning of the
  210.          * queue), so in that case the following call will do nothing.
  211.          */
  212.  
  213.         mv2front( minprot );
  214.         }
  215.     }
  216.     }
  217.  
  218.  
  219. /* cmptmps - compress template table entries
  220.  *
  221.  * synopsis
  222.  *    cmptmps();
  223.  *
  224.  *  template tables are compressed by using the 'template equivalence
  225.  *  classes', which are collections of transition character equivalence
  226.  *  classes which always appear together in templates - really meta-equivalence
  227.  *  classes.  until this point, the tables for templates have been stored
  228.  *  up at the top end of the nxt array; they will now be compressed and have
  229.  *  table entries made for them.
  230.  */
  231.  
  232. void cmptmps()
  233.  
  234.     {
  235.     int tmpstorage[CSIZE + 1];
  236.     register int *tmp = tmpstorage, i, j;
  237.     int totaltrans, trans;
  238.  
  239.     peakpairs = numtemps * numecs + tblend;
  240.  
  241.     if ( usemecs )
  242.     {
  243.     /* create equivalence classes base on data gathered on template
  244.      * transitions
  245.      */
  246.  
  247.     nummecs = cre8ecs( tecfwd, tecbck, numecs );
  248.     }
  249.     
  250.     else
  251.     nummecs = numecs;
  252.  
  253.     if ( lastdfa + numtemps + 1 >= current_max_dfas )
  254.     increase_max_dfas();
  255.  
  256.     /* loop through each template */
  257.  
  258.     for ( i = 1; i <= numtemps; ++i )
  259.     {
  260.     totaltrans = 0;    /* number of non-jam transitions out of this template */
  261.  
  262.     for ( j = 1; j <= numecs; ++j )
  263.         {
  264.         trans = tnxt[numecs * i + j];
  265.  
  266.         if ( usemecs )
  267.         {
  268.         /* the absolute value of tecbck is the meta-equivalence class
  269.          * of a given equivalence class, as set up by cre8ecs
  270.          */
  271.         if ( tecbck[j] > 0 )
  272.             {
  273.             tmp[tecbck[j]] = trans;
  274.  
  275.             if ( trans > 0 )
  276.             ++totaltrans;
  277.             }
  278.         }
  279.  
  280.         else
  281.         {
  282.         tmp[j] = trans;
  283.  
  284.         if ( trans > 0 )
  285.             ++totaltrans;
  286.         }
  287.         }
  288.  
  289.     /* it is assumed (in a rather subtle way) in the skeleton that
  290.      * if we're using meta-equivalence classes, the def[] entry for
  291.      * all templates is the jam template, i.e., templates never default
  292.      * to other non-jam table entries (e.g., another template)
  293.      */
  294.  
  295.     /* leave room for the jam-state after the last real state */
  296.     mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  297.     }
  298.     }
  299.  
  300.  
  301.  
  302. /* expand_nxt_chk - expand the next check arrays */
  303.  
  304. void expand_nxt_chk()
  305.  
  306.     {
  307.     register int old_max = current_max_xpairs;
  308.  
  309.     current_max_xpairs += MAX_XPAIRS_INCREMENT;
  310.  
  311.     ++num_reallocs;
  312.  
  313.     nxt = reallocate_integer_array( nxt, current_max_xpairs );
  314.     chk = reallocate_integer_array( chk, current_max_xpairs );
  315.  
  316.     bzero( (char *) (chk + old_max),
  317.        MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  318.     }
  319.  
  320.  
  321. /* find_table_space - finds a space in the table for a state to be placed
  322.  *
  323.  * synopsis
  324.  *     int *state, numtrans, block_start;
  325.  *     int find_table_space();
  326.  *
  327.  *     block_start = find_table_space( state, numtrans );
  328.  *
  329.  * State is the state to be added to the full speed transition table.
  330.  * Numtrans is the number of out-transitions for the state.
  331.  *
  332.  * find_table_space() returns the position of the start of the first block (in
  333.  * chk) able to accommodate the state
  334.  *
  335.  * In determining if a state will or will not fit, find_table_space() must take
  336.  * into account the fact that an end-of-buffer state will be added at [0],
  337.  * and an action number will be added in [-1].
  338.  */
  339.  
  340. int find_table_space( state, numtrans )
  341. int *state, numtrans;
  342.     
  343.     {
  344.     /* firstfree is the position of the first possible occurrence of two
  345.      * consecutive unused records in the chk and nxt arrays
  346.      */
  347.     register int i;
  348.     register int *state_ptr, *chk_ptr;
  349.     register int *ptr_to_last_entry_in_state;
  350.  
  351.     /* if there are too many out-transitions, put the state at the end of
  352.      * nxt and chk
  353.      */
  354.     if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
  355.     {
  356.     /* if table is empty, return the first available spot in chk/nxt,
  357.      * which should be 1
  358.      */
  359.     if ( tblend < 2 )
  360.         return ( 1 );
  361.  
  362.     i = tblend - numecs;    /* start searching for table space near the
  363.                  * end of chk/nxt arrays
  364.                  */
  365.     }
  366.  
  367.     else
  368.     i = firstfree;        /* start searching for table space from the
  369.                  * beginning (skipping only the elements
  370.                  * which will definitely not hold the new
  371.                  * state)
  372.                  */
  373.  
  374.     while ( 1 )        /* loops until a space is found */
  375.     {
  376.     if ( i + numecs > current_max_xpairs )
  377.         expand_nxt_chk();
  378.  
  379.     /* loops until space for end-of-buffer and action number are found */
  380.     while ( 1 )
  381.         {
  382.         if ( chk[i - 1] == 0 )    /* check for action number space */
  383.         {
  384.         if ( chk[i] == 0 )    /* check for end-of-buffer space */
  385.             break;
  386.  
  387.         else
  388.             i += 2;    /* since i != 0, there is no use checking to
  389.                  * see if (++i) - 1 == 0, because that's the
  390.                  * same as i == 0, so we skip a space
  391.                  */
  392.         }
  393.  
  394.         else
  395.         ++i;
  396.  
  397.         if ( i + numecs > current_max_xpairs )
  398.         expand_nxt_chk();
  399.         }
  400.  
  401.     /* if we started search from the beginning, store the new firstfree for
  402.      * the next call of find_table_space()
  403.      */
  404.     if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
  405.         firstfree = i + 1;
  406.  
  407.     /* check to see if all elements in chk (and therefore nxt) that are
  408.      * needed for the new state have not yet been taken
  409.      */
  410.  
  411.     state_ptr = &state[1];
  412.     ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  413.  
  414.     for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
  415.           ++chk_ptr )
  416.         if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  417.         break;
  418.  
  419.     if ( chk_ptr == ptr_to_last_entry_in_state )
  420.         return ( i );
  421.  
  422.     else
  423.         ++i;
  424.     }
  425.     }
  426.  
  427.  
  428. /* inittbl - initialize transition tables
  429.  *
  430.  * synopsis
  431.  *   inittbl();
  432.  *
  433.  * Initializes "firstfree" to be one beyond the end of the table.  Initializes
  434.  * all "chk" entries to be zero.  Note that templates are built in their
  435.  * own tbase/tdef tables.  They are shifted down to be contiguous
  436.  * with the non-template entries during table generation.
  437.  */
  438. void inittbl()
  439.  
  440.     {
  441.     register int i;
  442.  
  443.     bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
  444.  
  445.     tblend = 0;
  446.     firstfree = tblend + 1;
  447.     numtemps = 0;
  448.  
  449.     if ( usemecs )
  450.     {
  451.     /* set up doubly-linked meta-equivalence classes
  452.      * these are sets of equivalence classes which all have identical
  453.      * transitions out of TEMPLATES
  454.      */
  455.  
  456.     tecbck[1] = NIL;
  457.  
  458.     for ( i = 2; i <= numecs; ++i )
  459.         {
  460.         tecbck[i] = i - 1;
  461.         tecfwd[i - 1] = i;
  462.         }
  463.  
  464.     tecfwd[numecs] = NIL;
  465.     }
  466.     }
  467.  
  468.  
  469. /* mkdeftbl - make the default, "jam" table entries
  470.  *
  471.  * synopsis
  472.  *   mkdeftbl();
  473.  */
  474.  
  475. void mkdeftbl()
  476.  
  477.     {
  478.     int i;
  479.  
  480.     jamstate = lastdfa + 1;
  481.  
  482.     ++tblend; /* room for transition on end-of-buffer character */
  483.  
  484.     if ( tblend + numecs > current_max_xpairs )
  485.     expand_nxt_chk();
  486.  
  487.     /* add in default end-of-buffer transition */
  488.     nxt[tblend] = end_of_buffer_state;
  489.     chk[tblend] = jamstate;
  490.  
  491.     for ( i = 1; i <= numecs; ++i )
  492.     {
  493.     nxt[tblend + i] = 0;
  494.     chk[tblend + i] = jamstate;
  495.     }
  496.  
  497.     jambase = tblend;
  498.  
  499.     base[jamstate] = jambase;
  500.     def[jamstate] = 0;
  501.  
  502.     tblend += numecs;
  503.     ++numtemps;
  504.     }
  505.  
  506.  
  507. /* mkentry - create base/def and nxt/chk entries for transition array
  508.  *
  509.  * synopsis
  510.  *   int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  511.  *   mkentry( state, numchars, statenum, deflink, totaltrans );
  512.  *
  513.  * "state" is a transition array "numchars" characters in size, "statenum"
  514.  * is the offset to be used into the base/def tables, and "deflink" is the
  515.  * entry to put in the "def" table entry.  If "deflink" is equal to
  516.  * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  517.  * (i.e., jam entries) into the table.  It is assumed that by linking to
  518.  * "JAMSTATE" they will be taken care of.  In any case, entries in "state"
  519.  * marking transitions to "SAME_TRANS" are treated as though they will be
  520.  * taken care of by whereever "deflink" points.  "totaltrans" is the total
  521.  * number of transitions out of the state.  If it is below a certain threshold,
  522.  * the tables are searched for an interior spot that will accommodate the
  523.  * state array.
  524.  */
  525.  
  526. void mkentry( state, numchars, statenum, deflink, totaltrans )
  527. register int *state;
  528. int numchars, statenum, deflink, totaltrans;
  529.  
  530.     {
  531.     register int minec, maxec, i, baseaddr;
  532.     int tblbase, tbllast;
  533.  
  534.     if ( totaltrans == 0 )
  535.     { /* there are no out-transitions */
  536.     if ( deflink == JAMSTATE )
  537.         base[statenum] = JAMSTATE;
  538.     else
  539.         base[statenum] = 0;
  540.  
  541.     def[statenum] = deflink;
  542.     return;
  543.     }
  544.  
  545.     for ( minec = 1; minec <= numchars; ++minec )
  546.     {
  547.     if ( state[minec] != SAME_TRANS )
  548.         if ( state[minec] != 0 || deflink != JAMSTATE )
  549.         break;
  550.     }
  551.  
  552.     if ( totaltrans == 1 )
  553.     {
  554.     /* there's only one out-transition.  Save it for later to fill
  555.      * in holes in the tables.
  556.      */
  557.     stack1( statenum, minec, state[minec], deflink );
  558.     return;
  559.     }
  560.  
  561.     for ( maxec = numchars; maxec > 0; --maxec )
  562.     {
  563.     if ( state[maxec] != SAME_TRANS )
  564.         if ( state[maxec] != 0 || deflink != JAMSTATE )
  565.         break;
  566.     }
  567.  
  568.     /* Whether we try to fit the state table in the middle of the table
  569.      * entries we have already generated, or if we just take the state
  570.      * table at the end of the nxt/chk tables, we must make sure that we
  571.      * have a valid base address (i.e., non-negative).  Note that not only are
  572.      * negative base addresses dangerous at run-time (because indexing the
  573.      * next array with one and a low-valued character might generate an
  574.      * array-out-of-bounds error message), but at compile-time negative
  575.      * base addresses denote TEMPLATES.
  576.      */
  577.  
  578.     /* find the first transition of state that we need to worry about. */
  579.     if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  580.     { /* attempt to squeeze it into the middle of the tabls */
  581.     baseaddr = firstfree;
  582.  
  583.     while ( baseaddr < minec )
  584.         {
  585.         /* using baseaddr would result in a negative base address below
  586.          * find the next free slot
  587.          */
  588.         for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  589.         ;
  590.         }
  591.  
  592.     if ( baseaddr + maxec - minec >= current_max_xpairs )
  593.         expand_nxt_chk();
  594.  
  595.     for ( i = minec; i <= maxec; ++i )
  596.         if ( state[i] != SAME_TRANS )
  597.         if ( state[i] != 0 || deflink != JAMSTATE )
  598.             if ( chk[baseaddr + i - minec] != 0 )
  599.             { /* baseaddr unsuitable - find another */
  600.             for ( ++baseaddr;
  601.                   baseaddr < current_max_xpairs &&
  602.                   chk[baseaddr] != 0;
  603.                   ++baseaddr )
  604.                 ;
  605.  
  606.             if ( baseaddr + maxec - minec >= current_max_xpairs )
  607.                 expand_nxt_chk();
  608.  
  609.             /* reset the loop counter so we'll start all
  610.              * over again next time it's incremented
  611.              */
  612.  
  613.             i = minec - 1;
  614.             }
  615.     }
  616.  
  617.     else
  618.     {
  619.     /* ensure that the base address we eventually generate is
  620.      * non-negative
  621.      */
  622.     baseaddr = max( tblend + 1, minec );
  623.     }
  624.  
  625.     tblbase = baseaddr - minec;
  626.     tbllast = tblbase + maxec;
  627.  
  628.     if ( tbllast >= current_max_xpairs )
  629.     expand_nxt_chk();
  630.  
  631.     base[statenum] = tblbase;
  632.     def[statenum] = deflink;
  633.  
  634.     for ( i = minec; i <= maxec; ++i )
  635.     if ( state[i] != SAME_TRANS )
  636.         if ( state[i] != 0 || deflink != JAMSTATE )
  637.         {
  638.         nxt[tblbase + i] = state[i];
  639.         chk[tblbase + i] = statenum;
  640.         }
  641.  
  642.     if ( baseaddr == firstfree )
  643.     /* find next free slot in tables */
  644.     for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  645.         ;
  646.  
  647.     tblend = max( tblend, tbllast );
  648.     }
  649.  
  650.  
  651. /* mk1tbl - create table entries for a state (or state fragment) which
  652.  *            has only one out-transition
  653.  *
  654.  * synopsis
  655.  *   int state, sym, onenxt, onedef;
  656.  *   mk1tbl( state, sym, onenxt, onedef );
  657.  */
  658.  
  659. void mk1tbl( state, sym, onenxt, onedef )
  660. int state, sym, onenxt, onedef;
  661.  
  662.     {
  663.     if ( firstfree < sym )
  664.     firstfree = sym;
  665.  
  666.     while ( chk[firstfree] != 0 )
  667.     if ( ++firstfree >= current_max_xpairs )
  668.         expand_nxt_chk();
  669.  
  670.     base[state] = firstfree - sym;
  671.     def[state] = onedef;
  672.     chk[firstfree] = state;
  673.     nxt[firstfree] = onenxt;
  674.  
  675.     if ( firstfree > tblend )
  676.     {
  677.     tblend = firstfree++;
  678.  
  679.     if ( firstfree >= current_max_xpairs )
  680.         expand_nxt_chk();
  681.     }
  682.     }
  683.  
  684.  
  685. /* mkprot - create new proto entry
  686.  *
  687.  * synopsis
  688.  *   int state[], statenum, comstate;
  689.  *   mkprot( state, statenum, comstate );
  690.  */
  691.  
  692. void mkprot( state, statenum, comstate )
  693. int state[], statenum, comstate;
  694.  
  695.     {
  696.     int i, slot, tblbase;
  697.  
  698.     if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  699.     {
  700.     /* gotta make room for the new proto by dropping last entry in
  701.      * the queue
  702.      */
  703.     slot = lastprot;
  704.     lastprot = protprev[lastprot];
  705.     protnext[lastprot] = NIL;
  706.     }
  707.  
  708.     else
  709.     slot = numprots;
  710.  
  711.     protnext[slot] = firstprot;
  712.  
  713.     if ( firstprot != NIL )
  714.     protprev[firstprot] = slot;
  715.  
  716.     firstprot = slot;
  717.     prottbl[slot] = statenum;
  718.     protcomst[slot] = comstate;
  719.  
  720.     /* copy state into save area so it can be compared with rapidly */
  721.     tblbase = numecs * (slot - 1);
  722.  
  723.     for ( i = 1; i <= numecs; ++i )
  724.     protsave[tblbase + i] = state[i];
  725.     }
  726.  
  727.  
  728. /* mktemplate - create a template entry based on a state, and connect the state
  729.  *              to it
  730.  *
  731.  * synopsis
  732.  *   int state[], statenum, comstate, totaltrans;
  733.  *   mktemplate( state, statenum, comstate, totaltrans );
  734.  */
  735.  
  736. void mktemplate( state, statenum, comstate )
  737. int state[], statenum, comstate;
  738.  
  739.     {
  740.     int i, numdiff, tmpbase, tmp[CSIZE + 1];
  741.     Char transset[CSIZE + 1];
  742.     int tsptr;
  743.  
  744.     ++numtemps;
  745.  
  746.     tsptr = 0;
  747.  
  748.     /* calculate where we will temporarily store the transition table
  749.      * of the template in the tnxt[] array.  The final transition table
  750.      * gets created by cmptmps()
  751.      */
  752.  
  753.     tmpbase = numtemps * numecs;
  754.  
  755.     if ( tmpbase + numecs >= current_max_template_xpairs )
  756.     {
  757.     current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  758.  
  759.     ++num_reallocs;
  760.  
  761.     tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
  762.     }
  763.  
  764.     for ( i = 1; i <= numecs; ++i )
  765.     if ( state[i] == 0 )
  766.         tnxt[tmpbase + i] = 0;
  767.     else
  768.         {
  769.         transset[tsptr++] = i;
  770.         tnxt[tmpbase + i] = comstate;
  771.         }
  772.  
  773.     if ( usemecs )
  774.     mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );
  775.  
  776.     mkprot( tnxt + tmpbase, -numtemps, comstate );
  777.  
  778.     /* we rely on the fact that mkprot adds things to the beginning
  779.      * of the proto queue
  780.      */
  781.  
  782.     numdiff = tbldiff( state, firstprot, tmp );
  783.     mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  784.     }
  785.  
  786.  
  787. /* mv2front - move proto queue element to front of queue
  788.  *
  789.  * synopsis
  790.  *   int qelm;
  791.  *   mv2front( qelm );
  792.  */
  793.  
  794. void mv2front( qelm )
  795. int qelm;
  796.  
  797.     {
  798.     if ( firstprot != qelm )
  799.     {
  800.     if ( qelm == lastprot )
  801.         lastprot = protprev[lastprot];
  802.  
  803.     protnext[protprev[qelm]] = protnext[qelm];
  804.  
  805.     if ( protnext[qelm] != NIL )
  806.         protprev[protnext[qelm]] = protprev[qelm];
  807.  
  808.     protprev[qelm] = NIL;
  809.     protnext[qelm] = firstprot;
  810.     protprev[firstprot] = qelm;
  811.     firstprot = qelm;
  812.     }
  813.     }
  814.  
  815.  
  816. /* place_state - place a state into full speed transition table
  817.  *
  818.  * synopsis
  819.  *     int *state, statenum, transnum;
  820.  *     place_state( state, statenum, transnum );
  821.  *
  822.  * State is the statenum'th state.  It is indexed by equivalence class and
  823.  * gives the number of the state to enter for a given equivalence class.
  824.  * Transnum is the number of out-transitions for the state.
  825.  */
  826.  
  827. void place_state( state, statenum, transnum )
  828. int *state, statenum, transnum;
  829.  
  830.     {
  831.     register int i;
  832.     register int *state_ptr;
  833.     int position = find_table_space( state, transnum );
  834.  
  835.     /* base is the table of start positions */
  836.     base[statenum] = position;
  837.  
  838.     /* put in action number marker; this non-zero number makes sure that
  839.      * find_table_space() knows that this position in chk/nxt is taken
  840.      * and should not be used for another accepting number in another state
  841.      */
  842.     chk[position - 1] = 1;
  843.  
  844.     /* put in end-of-buffer marker; this is for the same purposes as above */
  845.     chk[position] = 1;
  846.  
  847.     /* place the state into chk and nxt */
  848.     state_ptr = &state[1];
  849.  
  850.     for ( i = 1; i <= numecs; ++i, ++state_ptr )
  851.     if ( *state_ptr != 0 )
  852.         {
  853.         chk[position + i] = i;
  854.         nxt[position + i] = *state_ptr;
  855.         }
  856.  
  857.     if ( position + numecs > tblend )
  858.     tblend = position + numecs;
  859.     }
  860.  
  861.  
  862. /* stack1 - save states with only one out-transition to be processed later
  863.  *
  864.  * synopsis
  865.  *   int statenum, sym, nextstate, deflink;
  866.  *   stack1( statenum, sym, nextstate, deflink );
  867.  *
  868.  * if there's room for another state one the "one-transition" stack, the
  869.  * state is pushed onto it, to be processed later by mk1tbl.  If there's
  870.  * no room, we process the sucker right now.
  871.  */
  872.  
  873. void stack1( statenum, sym, nextstate, deflink )
  874. int statenum, sym, nextstate, deflink;
  875.  
  876.     {
  877.     if ( onesp >= ONE_STACK_SIZE - 1 )
  878.     mk1tbl( statenum, sym, nextstate, deflink );
  879.  
  880.     else
  881.     {
  882.     ++onesp;
  883.     onestate[onesp] = statenum;
  884.     onesym[onesp] = sym;
  885.     onenext[onesp] = nextstate;
  886.     onedef[onesp] = deflink;
  887.     }
  888.     }
  889.  
  890.  
  891. /* tbldiff - compute differences between two state tables
  892.  *
  893.  * synopsis
  894.  *   int state[], pr, ext[];
  895.  *   int tbldiff, numdifferences;
  896.  *   numdifferences = tbldiff( state, pr, ext )
  897.  *
  898.  * "state" is the state array which is to be extracted from the pr'th
  899.  * proto.  "pr" is both the number of the proto we are extracting from
  900.  * and an index into the save area where we can find the proto's complete
  901.  * state table.  Each entry in "state" which differs from the corresponding
  902.  * entry of "pr" will appear in "ext".
  903.  * Entries which are the same in both "state" and "pr" will be marked
  904.  * as transitions to "SAME_TRANS" in "ext".  The total number of differences
  905.  * between "state" and "pr" is returned as function value.  Note that this
  906.  * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  907.  */
  908.  
  909. int tbldiff( state, pr, ext )
  910. int state[], pr, ext[];
  911.  
  912.     {
  913.     register int i, *sp = state, *ep = ext, *protp;
  914.     register int numdiff = 0;
  915.  
  916.     protp = &protsave[numecs * (pr - 1)];
  917.  
  918.     for ( i = numecs; i > 0; --i )
  919.     {
  920.     if ( *++protp == *++sp )
  921.         *++ep = SAME_TRANS;
  922.     else
  923.         {
  924.         *++ep = *sp;
  925.         ++numdiff;
  926.         }
  927.     }
  928.  
  929.     return ( numdiff );
  930.     }
  931.